using System.Collections.Generic;

namespace Test.ConsoleProgram.Algorithm.Solution
{
    [TestDescription("算法: 0841. 钥匙和房间")]
    public class No0841_CanVisitAllRooms : AbsBaseTestItem
    {
        /*
        有 N 个房间，开始时你位于 0 号房间。每个房间有不同的号码：0，1，2，...，N-1，并且房间里可能有一些钥匙能使你进入下一个房间。
        在形式上，对于每个房间 i 都有一个钥匙列表 rooms[i]，每个钥匙 rooms[i][j] 由 [0,1，...，N-1] 中的一个整数表示，其中 N = rooms.length。 钥匙 rooms[i][j] = v 可以打开编号为 v 的房间。
        最初，除 0 号房间外的其余所有房间都被锁住。
        你可以自由地在房间之间来回走动。
        如果能进入每个房间返回 true，否则返回 false。
        */

        public override void OnTest()
        {
            Assert.TestExe(CanVisitAllRooms, new List<IList<int>>()
            {
                new int[] {1},
                new int[] {2},
                new int[] {3},
                new int[] {},
            }, true);

            Assert.TestExe(CanVisitAllRooms, new List<IList<int>>()
            {
                new int[] {1,3},
                new int[] {3,0,1},
                new int[] {2},
                new int[] {0},
            }, false);
        }

        public bool CanVisitAllRooms(IList<IList<int>> rooms)
        {
            int n = rooms.Count, num = 0;
            bool[] vis = new bool[n];
            vis[0] = true;
            Queue<int> que = new Queue<int>();
            que.Enqueue(0);
            while (que.Count > 0)
            {
                int x = que.Dequeue();
                num++;
                foreach (int item in rooms[x])
                {
                    if (!vis[item])
                    {
                        vis[item] = true;
                        que.Enqueue(item);
                    }
                }
            }
            return num == n;
        }
    }
}
